FIG. 1A illustrates an example network 101 and an example routing table 102 for one of the nodes in the network. The illustrated network 101 is a packet-switched network comprising nodes A-H. In order for the nodes to be able to communicate with one another, each node needs to know how to address and transmit a packet onwards to a given destination node. To do so, each node needs to have some understanding of the network topology, so that it can determine the appropriate network link to use when transmitting a packet to a given destination. Routing protocols are employed to distribute knowledge about the topology of a network amongst the nodes of the network.
Two main classes of routing protocol exist: distance-vector routing protocols and link-state protocols. In a distance-vector routing protocol, each node maintains a routing table of nodes that each have an associated “next hop” node and an associated cost. In an initial condition, each node only knows about itself. In operation, each node periodically (e.g., every 30 seconds) informs its neighbors of its understanding of the network topology, by transmitting its routing table to each neighbor. In an initial iteration, each node initially informs its neighbors only of its own existence. Each neighbor uses this information to update its routing table by adding an entry for each neighbor node. At each subsequent iteration of the protocol, a given node's routing table is updated as more information is received from further reaches of the network. Eventually, when each node has learned about every other node, the protocol converges. Changes to the network (e.g., such as nodes going offline) are similarly shared, and eventually propagate through the network.
The routing information stored by node F is shown in table 102. Each row of the table associates a destination node with a cost and a “next hop” node. When node F transmits a packet to node A, node F utilizes the table 102 to determine that the next hop for the packet is via node D. Node F accordingly transmits the packet on the link connecting nodes F and D. Similarly, upon receipt of the packet, node D consults its routing table (not shown) to determine that the next hop for the packet is via node B. This process continues until the packet eventually reaches node A.
One of the problems with routing protocols such as distance-vector routing relates to the amount of information that must be communicated between nodes in order to maintain and distribute an accurate model of the network topology amongst the nodes. Note first that the number of rows in each routing table will here equal the number of nodes on the network 101. For example, table 102 includes eight rows. In order to respond to changes in the network (e.g., nodes or routes being added or removed), the routing protocol requires that the routing table of each node be shared with its neighbors periodically, such as every 5, 10, or 30 seconds. The shorter the time period (sometimes known as the “update interval”), the more responsive the protocol will be to network changes, but the more network bandwidth will be consumed by transmission of routing tables. In small networks, with only a few nodes, this may not be a problem. But in very large and/or highly dynamic networks, the operation of the routing protocol can impose significant overhead.
FIG. 1B illustrates operation of an example distance-vector routing protocol. More particularly, FIG. 1B depicts a simple network consisting of three nodes A-C. Initially, a link of cost 20 connects nodes A and B, and a link of cost 10 connects nodes B and C. A time t0, each of nodes A-C has a single-row routing table that includes only information about itself, which it then shares with its neighbors.
At time t1, having received the routing tables transmitted by its neighbors at time t0, each node adds rows to its table. For example, node A adds a row to its table reflecting the existence of node B on the network and the corresponding cost of 20. Node B similarly adds rows for nodes A and C. Node C adds a row for node B. Each node then shares its modified routing table with its neighbors.
At time t2, each node has received from its neighbors the routing table(s) transmitted at time t1. For node A, this means adding a row for node C, because it has now learned (from node B), that node C is reachable via node B. The cost field for node C is 30, reflecting the cost of 20 for the A-B link and the cost of 10 for the B-C link. Node B makes no changes to its tables, as it has learned no new information. Node C adds a row for node A, because it has now learned (from node B), that node A is reachable via node B.
At some time after time t2 and before time t3, the illustrated network is modified by adding a new link of cost 5 between nodes A and C. At time t3, nodes A and C become aware of this change and update their tables accordingly.
At time t4, each node has received from its neighbors the routing table(s) transmitted at time t3. Node A learns from node C that node C can communicate with node B at a cost of 10. This cost, added to the A-C link cost of 5 is a total of 15, and is lower than the previously stored cost of 20 for communicating with B. Accordingly, node A updates the row for node B to reflect the preferred route (via C) and updated cost of 15. By similar logic, node B updates its entry for node A, to reflect the fact that it can communicate with node A via node C at a total cost of 15.